package nl.unimaas.games.tron.engine;

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.Serializable;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

import nl.unimaas.games.tron.player.Player;

public class Board implements Cloneable, Serializable {
	private static final long serialVersionUID = 1159491603141557778L;
	
	/** This made a bit more sense in the previous implementation */
	public final static boolean EMPTY = false, WALL = true;
	
	/** Sequence of rows */
	public final boolean[] board;
	public final int width, height;
	private final int[] playerPositions;
	private final int[] start;
	/** Name of this board */
	private String name = null;
	/** ArrayList used by the move helper functions. This way, we don't have to create a new object for every move call */
	private final ArrayList<Integer> moves = new ArrayList<Integer>(4);
	
	public final static int MOVE_NONE = 0;
	public final static int MOVE_LEFT = -1;
	public final static int MOVE_RIGHT = 1;
	public final static int MOVE_UP = -2;
	public final static int MOVE_DOWN = 2;
	
	public Board(int w, int h) {
		board = new boolean[w * h];
		width = w;
		height = h;
		playerPositions = new int[2];
		start = new int[2];
	}
	
	public Board(boolean[] board, int w, int h) {
		this(board, w, h, new int[2], new int[2]);
	}
	
	public Board(boolean[] board, int w, int h, int[] playerPositions) {
		this(board, w, h, playerPositions, new int[2]);
	}
	
	public Board(boolean[] board, int w, int h, int[] playerPositions, int[] startPositions) {
		this.board = board;
		this.width = w;
		this.height = h;
		this.playerPositions = playerPositions;
		this.start = startPositions;
	}
	
	protected Board(Board board) {
		this.board = board.board;
		this.width = board.getWidth();
		this.height = board.getHeight();
		this.playerPositions = board.playerPositions;
		this.start = board.start;
	}
	
	public boolean[] getBoard() {
		return board;
	}

	public int getPlayerPosition(Player p) {
		return playerPositions[p.getNumber()];
	}
	
	public int getPlayerPosition(int playerNr) {
		return playerPositions[playerNr];
	}
	
	public boolean isValidPosition(int x, int y) {
		return (x >= 0 && y >= 0 && x <= getWidth() && y <= getHeight());
	}
	
	public boolean isValidPlayerMove(int x, int y, Player p) {
		int pos = getPlayerPosition(p);
		return (getManhattanDistance(x, y, posToX(pos), posToY(pos)) == 1 && isValidPosition(x, y) && isEmpty(x, y)); 
	}
	
	public void performMove(Player p, int m) {
		int pos = getPlayerPosition(p);
		performMove(posToX(pos), posToY(pos), m, p.getNumber());
	}
	
	public void performMove(int playerNr, int m) {
		int pos = getPlayerPosition(playerNr);
		performMove(posToX(pos), posToY(pos), m, playerNr, true);
	}
	
	public void performMove(int playerNr, int m, boolean check) {
		int pos = getPlayerPosition(playerNr);
		performMove(posToX(pos), posToY(pos), m, playerNr, check);
	}
	
	public int getPositionFromPlayerMove(Player p, int m) {
		int pos = getPlayerPosition(p);
		return getPositionFromMove(posToX(pos), posToY(pos), m);
	}
	
	public void performMove(int x, int y, int m, int playerNr) {
		performMove(x, y, m, playerNr, true);
	}
	
	public void performMove(int x, int y, int m, int playerNr, boolean check) {
		switch (m) {
		case MOVE_LEFT:
			x--;
			break;
		case MOVE_RIGHT:
			x++;
			break;
		case MOVE_UP:
			y--;
			break;
		case MOVE_DOWN:
			y++;
			break;
		}

		if (check) {
			if (isValidPosition(x, y))
				if (isEmpty(x, y))
					placePlayerWall(x, y, playerNr);
				else
					throw new IllegalStateException(String.format("move position of P%d contains a wall (%d, %d) %s", playerNr, x, y, m));
			else
				throw new IllegalStateException(String.format("invalid position after move to (%d, %d) %s", x, y, m));
		}
		else
			placePlayerWall(x, y, playerNr);
	}	
	
	public void placeWall(int x, int y) {
		board[xyToPos(this, x, y)] = WALL;
	}
	
	public void placePlayerWall(int x, int y, int playerNr) {
		board[xyToPos(this, x, y)] = WALL;
		playerPositions[playerNr] = xyToPos(x, y);
	}
	
	public void placePlayerWall(int x, int y, Player p) {
		placePlayerWall(x, y, p.getNumber());
	}
	
	public void removeWall(int x, int y) {
		board[xyToPos(this, x, y)] = EMPTY;
	}
	
	public boolean isEmpty(int x, int y) {
		return (board[xyToPos(this, x, y)] == EMPTY);
	}
	
	public boolean isWall(int x, int y) {
		return (board[xyToPos(this, x, y)] != EMPTY);
	}
	
	public boolean isPlayerWall(int x, int y) {
		return (board[xyToPos(this, x, y)] != EMPTY && board[xyToPos(this, x, y)] != WALL);
	}
	
	//TODO 
	public boolean isWallOfPlayer(int x, int y, int playerNr) {
		return (board[xyToPos(this, x, y)] == WALL);
	}
	
	public boolean getField(int x, int y) {
		return board[xyToPos(this, x, y)];
	}
	
	public boolean isSuicideMove(int sx, int sy, int tx, int ty) {
		if (board[xyToPos(this, tx, ty)] != EMPTY)
			return true;
		if (sx != tx - 1 && board[xyToPos(this, tx - 1, ty)] == EMPTY)
			return false;
		if (sx != tx + 1 && board[xyToPos(this, tx + 1, ty)] == EMPTY)
			return false;
		if (sy != ty - 1 && board[xyToPos(this, tx, ty - 1)] == EMPTY)
			return false;
		if (sy != ty + 1 && board[xyToPos(this, tx, ty + 1)] == EMPTY)
			return false;
		return true;
	}
	
	public ArrayList<Integer> getValidPlayerMoves(Player p) {
		 int pos = getPlayerPosition(p);
		 return getValidMoves(posToX(pos), posToY(pos));
	}
	
	public ArrayList<Integer> getValidMoves(int x, int y) {
		moves.clear();

		 if (board[xyToPos(this, x - 1, y)] == EMPTY)
			 moves.add(MOVE_LEFT);
		 if (board[xyToPos(this, x, y - 1)] == EMPTY)
			 moves.add(MOVE_UP);
		 if (board[xyToPos(this, x + 1, y)] == EMPTY)
			 moves.add(MOVE_RIGHT);
		 if (board[xyToPos(this, x, y + 1)] == EMPTY)
			 moves.add(MOVE_DOWN);
		 return moves;
	}
	
	/** Excludes suicidial moves */
	public ArrayList<Integer> getValidMovesFiltered(int x, int y) {
		 moves.clear();
		 if (getField(this, x - 1, y) == EMPTY && !isSuicideMove(x, y, x - 1, y))
			 moves.add(MOVE_LEFT);
		 if (getField(this, x, y - 1) == EMPTY && !isSuicideMove(x, y, x, y - 1))
			 moves.add(MOVE_UP);
		 if (getField(this, x + 1, y) == EMPTY && !isSuicideMove(x, y, x + 1, y))
			 moves.add(MOVE_RIGHT);
		 if (getField(this, x, y + 1) == EMPTY && !isSuicideMove(x, y, x, y + 1))
			 moves.add(MOVE_DOWN);
		 return moves;
	}
	
	public ArrayList<Integer> getValidPlayerMovePositions(Player p) {
		int pos = getPlayerPosition(p);
		return getValidMovePositions(posToX(pos), posToY(pos));
	}
	
	public ArrayList<Integer> getValidMovePositions(int x, int y) {
		 ArrayList<Integer> pos = moves;
		 pos.clear();
		 if (isEmpty(x - 1, y))
			 pos.add(xyToPos(x - 1, y));
		 if (isEmpty(x, y - 1))
			 pos.add(xyToPos(x, y- 1));
		 if (isEmpty(x + 1, y))
			 pos.add(xyToPos(x + 1, y));
		 if (isEmpty(x, y + 1))
			 pos.add(xyToPos(x, y + 1));
		 return pos;
	}
	
	private final ArrayList<int[]> pos = new ArrayList<int[]>(4);
	public ArrayList<int[]> getValidMovePositionsXY(int x, int y) {
		  pos.clear();

		 if (isEmpty(x - 1, y))
			 pos.add(new int[] {x - 1, y});
		 if (isEmpty(x, y - 1))
			 pos.add(new int[] {x, y- 1});
		 if (isEmpty(x + 1, y))
			 pos.add(new int[] {x + 1, y});
		 if (isEmpty(x, y + 1))
			 pos.add(new int[] {x, y + 1});
		 return pos;
	}
	public int getValidMoveCount(int x, int y) {
		 int count = 0;
		 if (isEmpty(x - 1, y))
			 count++;
		 if (isEmpty(x, y - 1))
			 count++;
		 if (isEmpty(x + 1, y))
			 count++;
		 if (isEmpty(x, y + 1))
			 count++;
		 return count;
	}
	
	public ArrayList<Integer> getValidMovePositions(int x, int y, boolean filterSuicide) {
		 ArrayList<Integer> pos = moves;
		 pos.clear();
		 if (isEmpty(x - 1, y) && (!filterSuicide || !isSuicideMove(x, y, x - 1, y)))
			 pos.add(xyToPos(x - 1, y));
		 if (isEmpty(x, y - 1) && (!filterSuicide || !isSuicideMove(x, y, x, y - 1)))
			 pos.add(xyToPos(x, y - 1));
		 if (isEmpty(x + 1, y) && (!filterSuicide || !isSuicideMove(x, y, x + 1, y)))
			 pos.add(xyToPos(x + 1, y));
		 if (isEmpty(x, y + 1) && (!filterSuicide || !isSuicideMove(x, y, x, y + 1)))
			 pos.add(xyToPos(x, y + 1));
		 return pos;
	}
	
	/** Returns the number of walls adjacent to this cell */
	public int getWallCount(int x, int y) {
		int count = 0;
		if (!isEmpty(x - 1, y))
			 count++;
		 if (!isEmpty(x, y - 1))
			 count++;
		 if (!isEmpty(x + 1, y))
			 count++;
		 if (!isEmpty(x, y + 1))
			 count++;
		 return count;
	}
	
	public int getFreeCount(int x, int y) {
		return 4 - getWallCount(x, y);
	}
	
	public void setStartPosition(int[] pos) {
		start[0] = pos[0];
		start[1] = pos[1];
	}
	
	public int[] getStartPositions() {
		return start;
	}
	
	public void setStartPositions(int[] pos) {
		start[0] = pos[0];
		start[1] = pos[1];
	}
	
	public String getName() {
		return name;
	}
	
	public void setName(String name) {
		this.name = name;
	}
	
	/** 
	 * ..X
	 * .OX
	 * .XX etc.
	 *  */
	public boolean isWallhugPosition(int x, int y) {
		if (getFreeCount(x, y) > 2)
			return false;
		else if (isEmpty(x - 1, y) && isEmpty(x + 1, y))
			return false;
		else if (isEmpty(x, y - 1) && isEmpty(x, y + 1))
			return false;
		else
			return true;
	}
	
	public boolean isArticulationPoint(int x, int y) {
		if (getField(this, x - 1, y) == EMPTY && isIsolatingMove(x, y, x - 1, y))
			return true;
		else if (getField(this, x + 1, y) == EMPTY && isIsolatingMove(x, y, x + 1, y))
			return true;
		else if (getField(this, x, y - 1) == EMPTY && isIsolatingMove(x, y, x, y - 1))
			return true;
		else if (getField(this, x, y + 1) == EMPTY && isIsolatingMove(x, y, x, y + 1))
			return true;
		return false;
	}
	
	/** Returns whether we are moving into a position which cuts us off from other move positions */
	public boolean isIsolatingMove(int ox, int oy, int tx, int ty) {
		//o-pos contains more than one free space

		if (getFreeCount(tx, ty) == 1) {
			//check for turns. turns are good for you
			if (ox != tx) {
				if (!isEmpty(tx, ty - 1) && !isEmpty(tx, ty + 1))
					return true;
			}
			else {
				if (!isEmpty(tx - 1, ty) && !isEmpty(tx + 1, ty))
					return true;
			}
		}
			
		if (ox != tx) {
			if (!isEmpty(tx, ty - 1) && isEmpty(ox, oy - 1))
				return true;
			if (!isEmpty(tx, ty + 1) && isEmpty(ox, oy + 1))
				return true;
			return false;
		}
		else {
			if (!isEmpty(tx - 1, ty) && isEmpty(ox - 1, oy))
				return true;
			if (!isEmpty(tx + 1, ty) && isEmpty(ox + 1, oy))
				return true;
			return false;
		}
	}
	
	public int getFreeSpace(int x, int y) {
		boolean[] shadowBoard = Board.cloneArray(board);
		return spaceStep(shadowBoard, x, y);
	}
	
	public int getFreeSpace(int ox, int oy, int tx, int ty) {
		boolean[] shadowBoard = Board.cloneArray(board);
		shadowBoard[xyToPos(this, ox, oy)] = WALL;
		return spaceStep(shadowBoard, tx, ty);
	}
	
	private int spaceStep(boolean[] shadowBoard, int x, int y) {
		shadowBoard[xyToPos(this, x, y)] = WALL;
		int space = 1;
		if (shadowBoard[xyToPos(this, x - 1, y)] == EMPTY)
			space += spaceStep(shadowBoard, x - 1, y);
		if (shadowBoard[xyToPos(this, x + 1, y)] == EMPTY)
			space += spaceStep(shadowBoard, x + 1, y);
		if (shadowBoard[xyToPos(this, x, y - 1)] == EMPTY)
			space += spaceStep(shadowBoard, x, y - 1);
		if (shadowBoard[xyToPos(this, x, y + 1)] == EMPTY)
			space += spaceStep(shadowBoard, x, y + 1);
		return space;
	}
	
	public int getWidth() {
		return width;
	}
	
	public int getHeight() {
		return height;
	}
	
	/** Returns a new board with this board's array */
	public Board shallowClone() {
		return new Board(board, width, height);
	}
	
	public void print() {
		int x1 = posToX(playerPositions[0]), x2 = posToX(playerPositions[1]);
		int y1 = posToY(playerPositions[0]), y2 = posToY(playerPositions[1]);
		
		int w = width, h = height;
		for (int y = 0; y < h; y++) {
			for (int x = 0; x < w; x++) {
				if (x == x1 && y == y1)
					System.out.printf("P0 ");
				else if (x == x2 && y == y2)
					System.out.printf("P1 ");
				else
					System.out.printf("%2d ", getField(this, x, y));
			}
			System.out.println();
		}
	}
	
	/** Returns a new board with this board's byte array and properties */
	@Override
	public Board clone() {
		Board b = new Board(board, width, height, playerPositions, start);
		b.setName(name);
		return b;
	}
	
	/** Returns a new board with a new byte array based on the old one */
	public Board deepClone(boolean inheritProperties) {
		int w = width, h = height;
		boolean[] newBoard = new boolean[w * h];
		
		System.arraycopy(board, 0, newBoard, 0, w * h);
		int[] playerPositions = this.playerPositions.clone();
		Board b = new Board(newBoard, width, height, playerPositions);
		if (inheritProperties) {
			b.setStartPositions(start);
			b.setName(name);
		}
		return b;
	}
	
	public void copyTo(Board b, boolean inheritProperties) {
		int w = width, h = height;
		if (b.width != w || b.height != h)
			throw new IllegalStateException("boards sizes do not match");
		
		System.arraycopy(board, 0, b.board, 0, w * h);
		System.arraycopy(playerPositions, 0, b.playerPositions, 0, 2);
		
		if (inheritProperties) {
			b.setStartPositions(start);
			b.setName(name);
		}
	}
	
	public boolean[] getClonedBoardArray() {
		int w = width;
		int h = height;
		boolean[] newBoard = new boolean[w * h];
		System.arraycopy(board, 0, newBoard, 0, w * h);
		return newBoard;
	}
	
	@Override
	public boolean equals(Object obj) {
		if (obj == this)
			return true;
		if (!(obj instanceof Board))
			return false;
		Board other = (Board) obj;
		if (other.getWidth() != getWidth() || other.getHeight() != getHeight())
			return false;
		for (int x = 0; x < getWidth(); x++)
			for (int y = 0; y < getHeight(); y++)
				if (board[xyToPos(this, x, y)] != other.board[xyToPos(this, x, y)])
					return false;
		return true;
	}
	
	public static Board fromFile(String file) throws FileNotFoundException {
		file = file.toLowerCase();
		if (file.endsWith(".txt")) {
			//Google AI Tron map
			FileReader fr = new FileReader(file);
			BufferedReader br = new BufferedReader(fr);
			try {
				//get map size
				String line = br.readLine();
				Pattern numPattern = Pattern.compile("\\d+");
				Matcher numMatcher = numPattern.matcher(line);
				numMatcher.find();
				int w = Integer.parseInt(numMatcher.group());
				numMatcher.find();
				int h = Integer.parseInt(numMatcher.group());
				final boolean[] board = new boolean[w * h];
				int[] playerPositions = new int[2];
				//parse level
				for (int y = 0; y < h; y++) {
					line = br.readLine();
					if (line != null) {
						for (int x = 0; x < line.length(); x++) {
							char c = line.charAt(x);
							switch (c) {
							case ' ':
								board[w * y + x] = EMPTY;
								break;
							case '#':
								board[w * y + x] = WALL;
								break;
							case '1':
								board[w * y + x] = EMPTY;
								playerPositions[0] = Board.xyToPos(w, x, y);
								break;
							case '2':
								board[w * y + x] = EMPTY;
								playerPositions[1] = Board.xyToPos(w, x, y);
								break;
							default:
								throw new IllegalStateException();
							}
						}
					}
					else
						break;
				}
				Board b;
				b = new Board(board, w, h);
				b.setStartPositions(playerPositions);
				b.setName(file);
				return b;
			}
			catch (Exception ex) {
				ex.printStackTrace();
				System.out.println(ex);
				return null;
			}
			finally {
				try {
					fr.close();
				} catch (IOException e) {
				}
			}
		}
		else
			throw new IllegalArgumentException();
	}
	
	public static int getMoveFromPositions(int ox, int oy, int tx, int ty) {
		if (ox != tx) {
			if (ox < tx)
				return MOVE_RIGHT;
			else
				return MOVE_LEFT;
		}
		else {
			if (oy < ty)
				return MOVE_DOWN;
			else
				return MOVE_UP;
		}
	}
	
	public int getPositionFromMove(int x, int y, int m) {
		if (m < 0) {
			if (m == Board.MOVE_LEFT)
				return Board.xyToPos(width, x - 1, y);
			else
				return Board.xyToPos(width, x, y - 1);
		}
		else {
			if (m == Board.MOVE_RIGHT)
				return Board.xyToPos(width, x + 1, y);
			else
				return Board.xyToPos(width, x, y + 1);
		}
	}
	
	public final static int getManhattanDistance(int x1, int y1, int x2, int y2) {
		return (Math.abs(x1 - x2) + Math.abs(y1 - y2));
	}
	
	public int posToX(int boardpos) {
		return boardpos % width;
	}
	
	public int posToY(int boardpos) {
		return boardpos / width;
	}
	
	public int xyToPos(int x, int y) {
		return y * width + x;
	}
	
	
	
	public final static boolean hasAdjacentWall(boolean[] board, int w, int x, int y) {
		return (board[w * y + x - 1] == WALL
				|| board[w * y + x + 1] == WALL 
				|| board[w * (y - 1) + x] == WALL 
				|| board[w * (y + 1) + x] == WALL);
	}
	
	public static boolean hasAdjacentEmptyField(boolean[] board, int w, int x, int y) {
		return (board[w * y + x - 1] == EMPTY
				|| board[w * y + x + 1] == EMPTY 
				|| board[w * (y - 1) + x] == EMPTY 
				|| board[w * (y + 1) + x] == EMPTY);
	}
	
	public final static boolean getField(Board b, int x, int y) {
		return b.board[b.width * y + x];
	}
	
	public final static void setField(Board b, int x, int y, boolean value) {
		b.board[b.width * y + x] = value;
	}
	
	public final static int xyToPos(Board b, int x, int y) {
		return b.width * y + x;
	}
	
	public final static int xyToPos(int w, int x, int y) {
		return w * y + x;
	}
	
	public final static int posToX(Board b, int pos) {
		return pos % b.width;
	}
	
	public final static int posToX(int w, int pos) {
		return pos % w;
	}
	
	public final static int posToY(Board b, int pos) {
		return pos / b.width;
	}
	
	public final static int posToY(int w, int pos) {
		return pos / w;
	}
		
	public static void printBoardArray(short[] board, int w) {
		int h = board.length / w;
		for (int y = 0; y < h; y++) {
			for (int x = 0; x < w; x++) {
				System.out.printf("%5d ", board[w * y + x]);
			}
			System.out.println();
		}
	}
	
	public static void printBoardArray(long[][] board) {
		int w = board.length, h = board[0].length;
		for (int y = 0; y < h; y++) {
			for (int x = 0; x < w; x++) {
				System.out.printf("%5d ", board[x][y]);
			}
			System.out.println();
		}
	}
	
	public static void printBoardArray(double[][] board) {
		int w = board.length, h = board[0].length;
		for (int y = 0; y < h; y++) {
			for (int x = 0; x < w; x++) {
				System.out.printf("%5f ", board[x][y]);
			}
			System.out.println();
		}
	}
	
	public static boolean[] cloneArray(boolean[] source) {
		boolean[] newBoard = new boolean[source.length];
		System.arraycopy(source, 0, newBoard, 0, source.length);
		return newBoard;
	}
	
	public static int[][] cloneArray(int[][] source) {
		int w = source.length;
		int h = source[0].length;
		int[][] newBoard = new int[w][];
		int[] y;
		for (int x = 0; x < w; x++) {
			y = new int[h];
			System.arraycopy(source[x], 0, y, 0, h);
			newBoard[x] = y;
		}
		return newBoard;
	}
	
	public static String moveToString(int move) {
		switch (move) {
		case MOVE_NONE:
			return "NONE";
		case MOVE_LEFT:
			return "LEFT";
		case MOVE_RIGHT:
			return "RIGHT";
		case MOVE_UP:
			return "UP";
		case MOVE_DOWN:
			return "DOWN";
		default:
			return "???";
		}
	}
}
